package algorithm.backtracing;

import java.util.ArrayList;
import java.util.List;

/**
 * 216. Combination Sum III
 * LeetCode: https://leetcode.com/problems/combination-sum-iii/
 * Difficulty: Medium
 * Related Topics: Array Backtracking
 *
 * 给两个参数 k 和 n
 * 从数字1~9里面，用k个不同的数字，组成和为n 的组合。
 * 找到所有不重复的组合
 *
 * 注意：
 * 1、数字只能使用一次
 * 2、结果集必须去重。比如，[1,2,4] 和 [2,4,1] 其实是一个，应该去重
 * 3、数字必须是1~9，不能大于9
 *
 * Created by yzy on 2019-05-06 19:44
 */
public class CombinationSumIII {

    public static void main(String[] args) {
        int k=2;
        int n=18;
        List<List<Integer>> lists = combinationSum3(k, n);
        System.out.println(lists);

    }

    /**
     * Runtime : 0ms, 100.0%
     * Memory : 36.8MB, 6.0%
     * @param k
     * @param n
     * @return
     */
    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> tmpList = new ArrayList<>();
        int initNum = 1;
        backTracing(k,n,result,tmpList, initNum);
        return result;
    }


    /**
     * 思路：
     * 每个数字只能用一次，并且要对结果去重。
     * 那么，数字就只能【从小到大正序使用】。
     * @param num
     * @param target
     * @param result
     * @param tmpList
     */
    public static void backTracing(int num, int target, List<List<Integer>> result, List<Integer> tmpList, int initNum){
        if(num==0 && target==0){
            result.add(new ArrayList<>(tmpList));
            return;
        }
        if(initNum > target){
            return;
        }
        int maxNum = target > 9 ? 9 : target;
        for(int i=initNum; i<=maxNum; i++){
            if(!tmpList.contains(i)){
                tmpList.add(i);
                backTracing(num-1, target-i, result, tmpList, i+1);
                tmpList.remove(tmpList.size()-1);
            }
        }
    }
}
